package 树.BST;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/*
解题思路：
    该题第一种解法。是我自己想出来的垃圾解法， 就把所有的节点的值放入list，再遍历list，进行相减。
    定义一个min，每次相减的结果与min进行比较。不断更新min。

    解法二：
        因为是二叉搜索树，所以我们用中序遍历，这样二叉树的节点值是从小到达排列的。
        我们只需要在每次进行中序遍历时，把当前值.val 与前一个元素的.val相减，并且更新min
 */
public class 二叉搜索树的最小绝对差_530 {

    //    public int getMinimumDifference(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        findAllRoot(list, root);//现在的list已经存有所有节点的值了
//        int min = Integer.MAX_VALUE;
//        for (int i = 0; i < list.size(); i++) {
//            for (int j = i + 1; j < list.size(); j++) {
//                int num = list.get(i) - list.get(j);
//                if (num < 0) {
//                    num = (-1) * num;
//                }
//
//                if (num < min) {
//                    min = num;
//                }
//
//            }
//        }
//        return min;
//
//    }
//
//    public void findAllRoot(List<Integer> list, TreeNode root) {//找到所有节点的值，并加入到list中
//        if (root == null) {
//            return;
//        }
//        list.add(root.val);
//        findAllRoot(list, root.left);
//        findAllRoot(list, root.right);
//    }
    TreeNode pre = null;
    int min = Integer.MAX_VALUE;//这俩变量要定义为成员变量，不然每次递归都会重置他们。

    public static void main(String[] args) {
        TreeNode t = new TreeNode(5, 4, 7);
        System.out.println(new 二叉搜索树的最小绝对差_530().getMinimumDifference(t));
    }

    public int getMinimumDifference(TreeNode root) {
        help(root);
        return min;
    }

    public void help(TreeNode root) {
        if (root == null) {
            return;
        }
        help(root.left);
        //中序遍历
        if (pre != null) {
            int cur = (root.val) - (pre.val);
            if (cur < 0) {
                cur = (-1) * cur;
            }
            if (cur < min) {
                min = cur;
            }
        }
        pre = root;
        help(root.right);

    }
}
